 template<class Type>class Queue;

template<class Type>class QueueNode{
friend class Queue<Type>;
private:
	Type data;
	QueueNode<Type>* link;
public:
	QueueNode(Type d = 0,QueueNode<Type>* next = NULL):data(d),link(next){
	}
};

template<class Type>class Queue{
private:
	QueueNode<Type>* front,* rear;
public:
	Queue():front(NULL),rear(NULL){
	}
	~Queue();
	void EnQueue(Type x);
	int DeQueue();
	int GetFront(Type& x);
	void MakeEmpty();
	int IsEmpty()const{
		return front == NULL;
	}
};

template<class Type>Queue<Type>::~Queue(){
	QueueNode<Type>* p;
	while(front != NULL){
		p = front;front = front->link;delete p;
	}	
}

template<class Type>void Queue<Type>::EnQueue(Type x){
	QueueNode<Type>* newnode = new QueueNode<Type>(x,NULL);
	if (front == NULL){
		front = rear = newnode;		
	}
	else{
		rear->link = newnode;
		rear = rear->link;
	}
}

template <class Type> int Queue<Type>::DeQueue(){
	if(IsEmpty())
		return 0;
	QueueNode<Type>* p = front;
	front = front->link;
	delete p;
	return 1;
}


template <class Type> int Queue<Type>::GetFront(Type& x){
	if(front == NULL)
		return 0;
	x = front->data;
	return 1;
}

template <class Type> void Queue<Type>::MakeEmpty(){
	QueueNode<Type>* p;
	while(front != NULL){
		p = front;front = front->link;delete p;
	}
}

